//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母组成 
// 
// Related Topics 字符串 动态规划 👍 5301 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution5 {

    /**
     * 正确写法
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int len = s.length();
        //记录是否是回文字串
        boolean[][] dp = new boolean[len][len];
        String result = "";
        int maxLen = 0; //记录最大长度
        for(int i = len-1; i >= 0; i--){
            for(int j = i; j < len; j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(j - i <= 1){
                        dp[i][j] = true;
                    } else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j] && j-i+1>maxLen){
                    maxLen = j-i+1;
                    result = s.substring(i,j+1);
                }
            }
        }
        return result;
    }

    /**
     * 法1：动态规划，与647回文字串一样
     *
     * 这种写法有问题，当s为cbbd时返回空字符，因为当字符串长度为2的时候没有初始化，
     * 例如s为aa,直接根据递推公式推出来的不对
     * @param s
     * @return
     */
    public String longestPalindrome1(String s) {
        int len = s.length();
        //记录是否是回文字串
        boolean[][] dp = new boolean[len][len];
        //初始化，仅初始化长度为1的情况了！！，这点与516最长回文子序列是不同的！！
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        String result = "";
        int maxLen = 0; //记录最大长度
        for(int i = len-1; i >= 0; i--){
            for(int j = i+1; j < len; j++){
                if(s.charAt(i) == s.charAt(j)){
                        dp[i][j] = dp[i+1][j-1];
                }
                if(dp[i][j] && j-i+1>maxLen){
                    maxLen = j-i+1;
                    result = s.substring(i,j+1);
                }
            }
        }
        return result;
    }

    /**
     * 法2：中心扩展法（双指针法）
     * @param args
     */

//    public String longestPalindrome1(String s) {
//        int len = s.length();
////        dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）
////        的子串是回文子串的长度
//        int[][] dp = new int[len][len];
//        for (int i = 0; i < len; i++) {
//            dp[i][i] = 1;
//        }
//        int m = 0, n =0;
//        int maxlen = 0;
//        for(int i = len-1; i >= 0; i--){
//            for(int j = i+1; j < len; j++){
//                if(s.charAt(i) == s.charAt(j)){
//                    dp[i][j] = dp[i+1][j-1]+2;
//                } else {
//                    dp[i][j] = dp[i+1][j-1];
//                }
//                if(dp[i][j] > maxlen){
//                    m = i;
//                    n = j;
//                }
//            }
//        }
//        return s.substring(m,n+1);
//    }
public static void main(String[] args) {
    new Solution5().longestPalindrome("cbbd");
}
}
//leetcode submit region end(Prohibit modification and deletion)
